\documentclass{article}
\usepackage{fullpage}
\usepackage{fixltx2e}
\usepackage[pdftex]{graphicx}
\newcommand{\HRule}{\rule{\linewidth}{0.5mm}}
\setlength{\pdfpagewidth}{\paperwidth}
\setlength{\pdfpageheight}{\paperheight} 
\renewcommand{\abstractname}{Problem}

\begin{document}
\begin{titlepage}
\begin{center}
\textsc{\Large Evolutionary Computing Final Project}\\[6cm]
\HRule \\[1cm]
{\huge \bfseries Fancy Dancing} \\[1cm]
\HRule \\[5cm]

\begin{minipage}{0.4\textwidth}
\begin{center} \large
Travis \textsc{Raines}
\end{center}
\end{minipage}
\begin{minipage}{0.4\textwidth}
\begin{center} \large
Conrad \textsc{Dean}
\end{center}
\end{minipage}
\end{center}
\end{titlepage}

\title{Evolutionary Computing Final Project}
\begin{abstract}
The Carleton Competitive Ballroom and Latin Dance Team must decide who whould dance with whom for every competition. At the moment, this falls under the responsibility of the team captains, who must take poorly self-reported data and determine a matching to try and pair everyone who wants to compete with a partner in a way that maximizes personal preferences and does not swamp any one person with too many partners. We decided to take this problem and write a system that can not only standardize the data conventions for the team captain, but also write a genetic algorithm to come up with a set of proposed best matches.
\end{abstract}
\section{Objective}
Write a genetic algorithm that can match dance partners based on various constraints and preferences. Since the algorithm is maximizing for multiple constraints, such as height difference, partner preferences, seniority, etc., it should return several best matches and allow for a person to pick a preferred outcome.

\section{Solution}
\subsection{Representation}
For our representation, we use networkX graphs. The preference matrix is converted into a bipartite meta-graph with leads on one side and follows on the other. Edges between every node from one side to the other represent the preference a lead has for a follow and vice-versa. An individual is another bipartite graph, but with only a subset of the meta-graph's edges to represent one possible matching between leads and follows. These graphs are constrained such that no node has degree $d > 2$. \\
The below example individual shows a random pairing where one side (follows) has more nodes than the other (a common problem), and so most leads have multiple partners. \\ \\
\begin{tabular}{l|c|c}
Colin & Lucy & SarahS.  \\
Collin & Lily & Valerie \\
Dan & Sarah R. &         \\
Kyle & Becky & Rochelle \\
Michael & Mira & Qwill  \\
Sean & Grace & Karen    \\
Travis & Emily & SarahR.\\
Tyler & Ainsley & Grace \\
\textsc{unpaired} & Katie & Kelly \\
\end{tabular}

\subsection{Fitness}
The fitness of a given individual is a composite of several different metrics: how well the preferences per individual were satisified, how acceptable the height differences are between partners, matching weighted pairings based on seniority and expected attendance to practices, and how many dancers have no partner at all:
\begin{enumerate}
\item Evaluating the satisfaction of individual preferences is determined by adding up the costs of the edges connecting each node. This is roughly equivalent to evaluating the max flow-max-cost over a bipartite graph with multiple sources and sinks to provide ensure everyone is matched. All edges have capacity one and costs corresponding to preference strength. Our algorithm takes the sum of all edge weights in the individual and divides it by the total number of partnerships to create an average satisfaction-per-partnership, so adding low-score matchings will tarnish the overall score, keeping unneccessary matchings out.
\item For height, the symmetric difference of the partners' heights for every partnership is summed and divided by the total number of partnerships to give the average height difference. This ensures that dancers are matched with other dancers of similar height whenever possible.
\item Weighted preferences are calculated similarly to preference, but with the edge costs modified in favor of experienced members and members who attend the most practices. Adding weight to the preferences of dedicated members ensures that they will more likely be paired with the partners they prefer since they are more likely show up to practices and have a greater desire to compete. However, the current weigting isn't based on any hard evidence, and needs to be tuned in the future to suit the wants of the team captains.
\item The final fitness metric gives an individual a exponentially-worse score for each person left unpaired. While unpaired dancers are often inevitable when there are more follows than leads or vice-versa, we want there to be as few of these as possible.
\end{enumerate}

\subsection{Mutation}
Since we never covered mutating graphs, and deap does not provide any utility to do so, we had to come up with our own method. To mutate an individual, it removes and adds random pairings that have not yet been tried (the list of untried pairings resets when it runs out.) After modifying the matching, it checks each node to try and enforce degree constraints: no person should have no partners, and no person should have more than two. This is run first on the larger side and then on the smaller side, and the latter may cause some on the larger side to be unpaired. This creates individuals that are always semi-valid, or less invalid than others.

\subsection{Selection}
For selection, we simply used the included algorithms in the deap package. SPEA2 and NSGA2 are selection methods that maintain diversity in a population while at the same time optimizing multi-objective problems such as ours. Through passing paramters to the program, you can select which method to use at runtime.
\section{Hypotheses}
\paragraph{The genetic algorithm has advantages over a deterministic algorithm}
As we didn't have enough time to write a deterministic version of our solution, we don't have anything to compare it to proper. However, a max-flow algorithm would only return one, optimal solution. To get this optimal solution, we would need to combine all metrics into one super cost, and this is difficult to fine-tune. The genetic algorithm will instead produce multiple solutions that optimize each objective individually. Furthermore, it may not be able to run the max flow algorithm on instances where not all dancers can be paired: since the pairing constraint relies on multiple sources and sinks, and some of those sinks will receive the necessary amount of flow, the algorithm will fail. It may be possible to modify the algorithm to return the best partial solution, but the out-of-the-box version won't work.

\paragraph{Representing partnerships}
We found that a graph, though memory intensive, was the best way to represent our individuals. (In the expected case there are fewer than 100 partners, so this works out alright.) By maintaining constraints on the degree of a node based on which half of the bipartite graph its located, we can account for illegal pairings. Manipulating individuals requires only adding and removing edges, which allows for a connected search space and is easy to implement.

\paragraph{Muli-objective selection is best}
Multi-objective, non-dominated selection methods such as NSGA2 and SPEA2, included in deap, allowed to easily optimize each fitness function without worrying about their interaction--as mentioned before, using a single fitness requires carefully weighting each component to make sure it does not dominate the others.

\section{Unexpected issues}
Major issues were technical rather than theoretical: deap does not work well with networkX graphs, and they had to be shoehorned into the Individual class, and some confusion with deap's specifications led us to not actually mutate any of the initial population for some time. Most theory changes were made in response to problems caused by the latter issue, and later reverted--the initial system remained mostly unchanged. The only major unrelated theory issue was using the average, rather than the total, for fitness metrics other than orphans--otherwise, extra, less optimal partnerships improve fitness.

\section{Conclusions}
Success. It's come up with good pairings based on real data from the competive dance team, and also performs well on naive examples where ther is an obvious answer. Once we have the web interface finalized, we will have a useful, shippable product.

\end{document}
